package LeetCode;

/**
 * @Author: Dijah
 * @Date: 2023/2/13 11:31
 * @Desc:买卖股票的最佳时机
 */
public class code121_maxProfit {
    public static int maxProfit_k(int[] prices){
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i - 1 == -1) {
                // base case
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }
        return dp[n - 1][0];
    }

    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) {
            return 0;
        }

        //记录今天之前买入的最小值
        int min = prices[0];
        int max = 0;
        //
        for(int i = 1; i<prices.length; i++){
            //记录今天卖出的获利，拿到最大
            max = Math.max(max,prices[i]-min);
            min = Math.min(min,prices[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int [] nums = {7,1,5,3,6,4};
        int i = maxProfit_k(nums);
        System.out.println(i);
    }
}
